package com.cjl.demo.data.structure;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>Copyright: All Rights Reserved</p>
 * <p>Company:    http://www.ronglian.com</p>
 * <p>Description:  面试题：将正整数n，拆分为任意正整数之和</p>
 * <p>Description:  如2拆分为1+1和2</p>
 * <p>Description:  如3拆分为1+1+1/1+2/2+1/3</p>
 * <p>Author:jlchen/陈金梁</p>
 * <p>Date:  2018/3/30</p>
 */
public class SplitOneDataToAnySumData {

        /**
         * <p>Description: 核心思想：使用递归，正整数n的拆解方式，为n-1基础上加1,或者在n-1基础上，将最后一位加1</p>
         * <p>@Author:jlchen/陈金梁</p>
         * @date 2018/3/30 21:28
         * @return
        */
      public List<String> splitOneDataToAnySumData( int i){
        List<String> resultList = new ArrayList<>();
        if(i == 1){
            resultList.add("1");
            return resultList;
        }
        List<String> dataList = splitOneDataToAnySumData(i -1);
        for(String tmp : dataList){
            if(tmp.length() ==1){
                Integer t = Integer.valueOf(tmp);
                resultList.add(tmp +"1");
                resultList.add(String.valueOf(t + 1));
            }else{
                Integer t = Integer.valueOf(tmp.substring(tmp.length()-2));
                resultList.add(tmp +1);
                resultList.add(tmp.substring(0,tmp.length() -2) + (t+1));
            }

        }
        return  resultList;
    }
    public static void main(String[] args) {
        SplitOneDataToAnySumData data = new SplitOneDataToAnySumData();
        List<String> result = data.splitOneDataToAnySumData(5);
        for(String s : result){
            System.out.println("args = [" + s + "]");
        }

//        List<String > result2 = data.splitOneDataToAnySumData();
    }
}
